package com.yx;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author yx
 * @date 2025-04-14 上午9:59
 * @description: 排序算法
 */
public class SortAlgorithmDemo {

    int[] nums = new int[]{51234, 312, 41234, 423, 524543, 5, 8, 2, 3333333};

    /*=====================选择排序=====================*/

    /**
     * 选择排序
     *
     * @param nums
     */
    public void selectionSort(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length - 1; i++) {//外循环：未排序区间为[i, n-1]
            int k = i;//最小值
            for (int j = k + 1; j < length; j++) {
                if (nums[k] > nums[j]) {
                    k = j;
                }
            }
            int temp = nums[i];
            nums[i] = nums[k];
            nums[k] = temp;
        }
    }

    @Test
    public void selectionSortTest() {
        selectionSort(nums);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    /*=====================冒泡排序=====================*/

    /**
     * 冒泡排序
     *
     * @param nums
     */
    public void bubbleSort(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length - 1; i++) {
            boolean isSort = true;//标记某轮没有交换，则已经排序完成
            for (int j = 0; j < length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    isSort = false;
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
            if (isSort) {
                break;
            }
        }
    }

    /**
     * 倒序冒泡排序
     *
     * @param nums
     */
    public void bubbleSortWithFlag(int[] nums) {
        int length = nums.length;
        for (int i = length - 1; i > 0; i--) {
            boolean isSort = true;//标记某轮没有交换，则已经排序完成
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    isSort = false;
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
            if (isSort) {
                break;
            }
        }
    }

    @Test
    public void bubbleSortTest() {
        bubbleSort(nums);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    /*=====================插入排序=====================*/

    /**
     * 插入排序
     *
     * @param nums
     */
    public void insertionSort(int[] nums) {
        int length = nums.length;
        for (int i = 1; i < length; i++) {//外层循环从第二个元素开始
            int base = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > base) {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = base;
        }
    }

    @Test
    public void insertionSortTest() {
        insertionSort(nums);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    /*=====================快速排序=====================*/

    /**
     * 元素交换
     *
     * @param nums
     * @param i
     * @param j
     */
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 哨兵划分
     *
     * @param nums
     * @param left
     * @param right
     * @return
     */
    public int partition(int[] nums, int left, int right) {
//        //优化项，取三位数的中间位，防止出现最差时间复杂度
//        int mid = medianThree(nums, left, left + (left - right) / 2, right);
//        swap(nums, left, mid);
        int base = nums[left];//以nums[left]为基数
        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= base) {//从右往左找首个小于基准数的元素
                j--;
            }
            while (i < j && nums[i] <= base) {//从左往右找首个大于基准数的元素
                i++;
            }
            swap(nums, i, j);
        }
        //将基准数交换至两子数组的分界线
        swap(nums, left, i);
        return i;//返回基准数的索引
    }

    /**
     * 快速排序
     *
     * @param nums
     * @param left
     * @param right
     */
    public void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int partition = partition(nums, left, right);
        //递归左子数组
        quickSort(nums, left, partition - 1);
        //递归右子数组
        quickSort(nums, partition + 1, right);
    }

    /**
     * 选取三个候选元素的中位数
     *
     * @param nums
     * @param left
     * @param right
     * @param mid
     * @return
     */
    public int medianThree(int nums[], int left, int right, int mid) {
        // 此处使用异或运算来简化代码
        // 异或规则为 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1
        if ((nums[left] < nums[right]) ^ (nums[left] < nums[right])) {
            return left;
        } else if ((nums[mid] < nums[left]) ^ (nums[mid] < nums[right])) {
            return mid;
        } else {
            return right;
        }
    }

    /**
     * 快速排序尾递归优化
     * 在某些输入下，快速排序可能占用空间较多
     * 仅对较短的子数组进行递归
     *
     * @param nums
     * @param left
     * @param right
     */
    public void quickSortTailRecursion(int[] nums, int left, int right) {
        while (left < right) {
            int pivot = partition(nums, left, right);
            //对两个数组中较短的那个执行快速排序
            if (pivot - left < right - pivot) {
                quickSortTailRecursion(nums, left, pivot - 1);//递归排序左子数组
                left = pivot + 1;//剩余未排序区间为 [pivot + 1, right]
            } else {
                quickSortTailRecursion(nums, pivot + 1, right);//递归排序右子数组
                right = pivot - 1;//剩余未排序区间为 [left, pivot - 1]
            }
        }
    }

    @Test
    public void quickSortTest() {
        quickSort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    @Test
    public void medianThreeTest() {
        int length = nums.length - 1;
        int i = medianThree(nums, 0, length / 2, length);
        System.out.println(i);
    }

    @Test
    public void quickSortTailRecursionTest() {
        quickSortTailRecursion(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    /*=====================归并排序=====================*/

    /**
     * 合并左子数组和右子数组
     *
     * @param nums
     * @param left
     * @param right
     * @param mid
     */
    public void merge(int[] nums, int left, int right, int mid) {
        //临时数组
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        //将左右子数组中的较小元素放入临时数组
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        //将剩余左子数组元素放入临时数组
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        //将剩余右子数组元素放入临时数组
        while (j <= right) {
            temp[k++] = nums[j++];
        }
        //将临时数组中的元素复制回原数组对应的区间
        for (k = 0; k < temp.length; k++) {
            nums[left + k] = temp[k];
        }
    }

    /**
     * 归并排序
     *
     * @param nums
     * @param left
     * @param right
     */
    public void mergeSort(int[] nums, int left, int right) {
        //终止条件
        if (left >= right) {
            return;
        }
        //划分阶段
        int mid = left + (right - left) / 2;
        //递归左子数组
        mergeSort(nums, left, mid);
        //递归右子数组
        mergeSort(nums, mid + 1, right);
        //合并左右子数组
        merge(nums, left, right, mid);
    }

    @Test
    public void mergeSortTest() {
        mergeSort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    /*=====================堆排序=====================*/

    /**
     * 堆化
     * 堆的长度n，从节点i开始，从顶至底堆化
     *
     * @param nums
     * @param n
     * @param i
     */
    public void siftDown(int[] nums, int n, int i) {
        while (true) {
            //判断节点 i, l, r 中值最大的节点，记为 max
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            int max = i;
            if (l < n && nums[l] > nums[max]) {
                max = l;
            }
            if (r < n && nums[r] > nums[max]) {
                max = r;
            }
            //若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
            if (max == i) {
                break;
            }
            //交换两节点
            int temp = nums[i];
            nums[i] = nums[max];
            nums[max] = temp;
            //循环向下堆化
            i = max;
        }
    }

    /**
     * 堆排序
     *
     * @param nums
     */
    void heapSort(int[] nums) {
        //建堆操作：堆化除叶节点以外的其他所有节点
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            siftDown(nums, nums.length, i);
        }
        //从堆中提取最大元素，循环n-1轮
        for (int i = nums.length - 1; i > 0; i--) {
            //交换根节点与最右叶节点（交换首元素与尾元素）
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            siftDown(nums, i, 0);
        }
    }

    @Test
    public void heapSortTest() {
        heapSort(nums);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    /*=====================桶排序=====================*/

    public void bucketSort(float[] nums) {
        //初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
        int k = nums.length / 2;
        List<List<Float>> bucketList = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            bucketList.add(new ArrayList<>());
        }
        //1.将数组元素分配到各个桶中
        for (float num : nums) {
            //输入数据范围为 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]
            int i = (int) (num * k);
            //将 num 添加进桶 i
            bucketList.get(i).add(num);
        }
        //2.对各个桶执行排序
        for (List<Float> bucket : bucketList) {
            Collections.sort(bucket);
        }
        //3.遍历桶合并结果
        int i = 0;
        for (List<Float> bucket : bucketList) {
            for (Float num : bucket) {
                nums[i++] = num;
            }
        }
    }

    @Test
    public void bucketSortTest() {
        float[] nums = {0.73f, 0.89f, 0.65f, 0.13f, 0.23f, 0.34f, 0.12f, 0.53f, 0.43f, 0.98f};
        bucketSort(nums);
        for (float num : nums) {
            System.out.println(num);
        }
    }

    /**
     * 计数排序
     *
     * @param nums
     */
    public void countingSortNaive(int[] nums) {
        //1. 获取最大值
        int max = 0;
        for (int num : nums) {
            max = Math.max(num, max);
        }
        //2. 统计各数字的出现次数
        int[] temp = new int[max + 1];
        for (int num : nums) {
            temp[num]++;
        }
        //3. 遍历 counter ，将各元素填入原数组 nums
        int k = 0;
        for (int i = 0; i < temp.length; i++) {
            int num = temp[i];
            for (int j = 0; j < num; j++) {
                nums[k++] = i;
            }
        }
    }

    @Test
    public void countingSortNaiveTest() {
        countingSortNaive(nums);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    /**
     * 完整版计数排序
     *
     * @param nums
     */
    public void countingSort(int[] nums) {
        //1. 获取nums中的最大值
        int max = 0;
        for (int num : nums) {
            max = Math.max(num, max);
        }
        // 2. 统计各数字的出现次数
        int[] counter = new int[max + 1];
        for (int num : nums) {
            counter[num]++;
        }
        //3. 求 counter 的前缀和，将“出现次数”转换为“尾索引”
        //即 counter[num]-1 是 num 在 res 中最后一次出现的索引
        for (int i = 0; i < max; i++) {
            counter[i + 1] += counter[i];
        }
        //4. 倒序遍历nums根据前缀和获取对应索引位置 并-1
        int length = nums.length;
        //初始化数组 res 用于记录结果
        int[] res = new int[length];
        for (int i = length - 1; i >= 0; i--) {
            int num = nums[i];
            res[counter[num] - 1] = num;// 将 num 放置到对应索引处
            counter[num]--;
        }
        //使用结果数组 res 覆盖原数组 nums
        for (int i = 0; i < length; i++) {
            nums[i] = res[i];
        }
    }

    @Test
    public void countingSortTest() {
        int[] nums = new int[]{1,3,4,5,2,3,1,2,3,4,2};
        countingSort(nums);
        for (int num : nums) {
            System.out.println(num);
        }
    }
}
